1. Field of the Invention
The present invention relates to a method for propagating switching activity information in a digital network, and more particularly to a method for computing and propagating signal and switching probabilities through components in a combinatorial logic circuit.
2. Description of the Related Art
In electronic systems, power consumption is one of the factors determining efficiency and functionality of the system. With the proliferation of wireless and hand-held electronic devices such as palm top computers, cellular telephones, etc., power consumption has become an important factor to be considered in designing and manufacturing such electronic devices. Since power consumption of such electronic devices directly relates to battery size and duration of usage of the devices between charges, battery life has become one of the most important factors in such electronic devices.
To choose a battery for an electronic device, the expected power consumption of the electronic device has to be accurately computed. In order to design power-efficient electronic devices, it is necessary to estimate and optimize power consumed in each component (i.e., IC) of an electronic device. Accurate computation of power consumption can improve battery life by enabling the design process to alleviate power-related problems in an electronic device, such as electron migration, circuit timing degradation due to voltage drops, hot-electron degradation, etc.
For fabrication of logic circuits in electronic devices, complementary metal oxide silicon (CMOS) technology is most commonly used. For CMOS devices, a primary source of power consumption is xe2x80x9cdynamic powerxe2x80x9d. Dynamic power is the power consumed when signals at inputs or output(s) of the CMOS circuit switch from one logic state to another logic state, for example, from logic xe2x80x9c0xe2x80x9d to logic xe2x80x9c1xe2x80x9d or from logic xe2x80x9c1xe2x80x9d to logic xe2x80x9c0xe2x80x9d.
A logic network performing a predetermined logic function may have a set of logic circuits each of which operates in accordance with a certain logic function. In such a logic network, a combinatorial logic function is performed by implementing a logic function of each logic circuit. Thus, to compute power consumed in such a logic network, it is necessary to compute power consumed in each of the logic circuits.
For computation of dynamic power (or switching power) in a logic circuit, it is necessary to compute the number of logic transitions per unit time of a signal at each node in the logic circuit. In terms of quantity, the number of logic transitions per unit time of a signal at Node i is called xe2x80x9cswitching probability (qi)xe2x80x9d. In a synchronous digital network, switching probability (qi) represents a fraction of clock cycles during which a signal at Node i makes a transition.
Another quantitative term related to the switching probability (qi) is xe2x80x9csignal probability (pi)xe2x80x9d at Node i. Signal probability (pi) represents a fraction of time during which a signal at Node i has a value of logic xe2x80x9c1xe2x80x9d. The signal and switching probabilities (pi, qi) at Node i are among quantities that are collectively known as xe2x80x9csignal statisticsxe2x80x9d of a signal at Node i.
Since dynamic power consumed in a logic circuit is substantially equal to summation of switching powers consumed in all the nodes of the logic circuit during transitions of signals at the nodes, power consumed in the logic circuit can be computed from the following equation:                     Power        =                              ∑            i                    ⁢                                    C              i                        ⁢                          xe2x80x83                        ⁢                          V              2                        ⁢                          xe2x80x83                        ⁢                          q              i                                                          (        1        )            
where, xe2x80x9cCixe2x80x9d is load capacitance, xe2x80x9cVxe2x80x9d is amount of voltage swing between logic xe2x80x9c0xe2x80x9d and logic xe2x80x9c1xe2x80x9d, and xe2x80x9cqixe2x80x9d is switching probability at Node i. In Equation (1), a product of Ci, V2, and qi is calculated with respect to Node i, and the summation is taken over all the nodes in the logic circuit.
To compute power consumed in a logic circuit using Equation (1), it is necessary to have values of switching probabilities at all nodes in the logic circuit. Assuming that signal statistics, including switching probabilities, at inputs of a logic circuit are known, power consumed in the logic circuit can be obtained using Equation (1) by computing switching probabilities at all nodes in the logic circuit. Such computation of switching probabilities at all the nodes can be accomplished by propagating the signal statistics at inputs of the logic circuit through various Boolean functions constituting a combinatorial function of the logic circuit. Thus, signal statistics of a logic circuit obtained from such a propagation depends on each Boolean function (1) and signal statistics at inputs of the logic circuit.
Conventional methods for propagating signal statistics, including signal and switching probabilities, into a logic circuit are disclosed, for example, in xe2x80x9cTransition Density: A New Measure of Activity in Digital Circuitsxe2x80x9d, by F. Najm, February 1993, IEEE, Vol. 12, No. 2, pp. 310-323 (hereinafter xe2x80x9cNajmxe2x80x9d); and xe2x80x9cEstimation of Activity for Static and Domino CMOS Circuits Considering Signal Correlations and Simultaneous Switchingxe2x80x9d, by T. Chou and K. Roy, October 1996, IEEE, Vol. 15, No. 10, pp. 1257-1264 (hereinafter xe2x80x9cChou et al.xe2x80x9d).
Najm discloses formulas to compute signal and switching probabilities at the output of a node in the logic circuit using signal and switching probabilities at the inputs of the node. Najm assumes that input signals of a logic circuit are statistically independent and that only one of the input signals may make a transition at any given time.
Chou et al., mentioning that the formulae proposed by Najm have limitations in handling simultaneous switching of input signals of a node, proposes a method for more accurately propagating signal and switching probabilities into a logic circuit by extending the result in Najm. In xe2x80x9cProbabilities Modeling of Dependencies During Switching Activity Analysisxe2x80x9d, by Marculescu et al., February 1998, IEEE, Vol. 17, No. 2, pp. 73-83, the method (formulae) proposed by Chou et al. has been modeled in terms of Markov processes to provide a solution for propagation of signal and switching probabilities considering spatial-temporal correlations in analysis of the propagation.
However, the conventional methods for propagating signal and switching probabilities at inputs into a logic circuit are difficult to apply in practice for computing power consumed in the logic circuit. For example, in a simulation of propagating signal and switching probabilities through a network using the conventional methods, vectors are obtained at inputs of the network and then used for computing signal and switching probabilities at each of intermediate inputs and outputs of the network. Such a simulation is a time consuming and costly process. The Markov based process or the Boolean difference based process leads to highly complex computations in implementing the propagation of signal and switching probabilities.
Therefore, a need exists for a method for propagating signal and switching probabilities at inputs through a logic network by using a less complex and less time-consuming method of computing signal and switching probabilities with respect to each of logic circuits in the logic network. Further, it will be advantageous to provide a method for estimating and optimizing power consumed in a logic network using the propagation of signal and switching probability through the logic network.
It is an object of the present invention to provide a method for computing and propagating signal and switching probabilities through logic circuits in a combinatorial network to obtain signal and switching probabilities at output of the network.
It is another object of the present invention to provide a method for estimating power consumed in a logic circuit using the method of propagating signal and switching probabilities through the logic circuit.
It is still anther object of the present invention to provide a method for optimizing power consumed in a logic circuit using the method of power estimation and propagation of signal and switching probabilities.
To achieve the above and other objects, the present invention provides a method for computing switching probability at an output of a logic circuit having multiple inputs and a predetermined function, the method comprising the steps of providing signal and switching probabilities at the inputs, creating a switching table having multiple entries each of which represents a transition status of a signal at the output of the circuit operating in accordance with the predetermined function, computing event probabilities with respect to each of the entries, wherein the event probabilities include a first event probability representing a probability of event that a signal at an input of the circuit switches, a second event probability representing a probability of event that a signal at an input of the circuit does not switch and is at a first value, and a third event probability representing a probability of event that a signal at an input of the circuit does not switch and is at a second value, and accumulating the event probabilities computed with respect to the plurality of entries to produce the switching probability at the output of the circuit.
The computation of event probabilities is preferably performed with respect to entries each representing that there is a transition in a signal at the output of the circuit, or with respect to entries each representing that there is no transition in a signal at the output of the circuit and subtracting from one (1) a value obtained by accumulating the event probabilities.
When the switching table includes input signal values represented with binary bits each of which is determined by values of the inputs and switching values represented with binary bits each of which is determined by switching status of each of the inputs, wherein each of the plurality of entries is determined by corresponding input signal value and switching value, the first event probability may be computed by setting each of the binary bits of a switching value to a predetermined logic value depending on switching status of a corresponding one of the plurality of inputs, detecting binary bits each having a predetermined logic value representing a switching at a corresponding one of the plurality of inputs, assigning an event probability of occurrence of the switching with respect to each of the binary bits detected, and multiplying event probabilities each of which is assigned to a corresponding one of the binary bits detected, whereby producing the first event probability. The second event probability may be computed by detecting binary bits each having a predetermined logic value representing that a signal at a corresponding one of the plurality inputs does not switch, detecting binary bits each having a logic high, assigning an event probability to each of the binary bits detected, the event probability representing a probability of event that a signal at an input corresponding to each of the binary bits detected does not switch and is at the logic high, and multiplying event probabilities each of which is assigned to a corresponding one of the binary bits detected, whereby producing the second event probability. The third event probability may be computed by detecting binary bits each having a logic low, assigning an event probability to each of the binary bits detected, the event probability representing a probability of event that a signal at an input corresponding to each of the binary bits detected does not switch and is at the logic low, and multiplying event probabilities each of which is assigned to a corresponding one of the binary bits detected, whereby producing the third event probability.
The creation of the switching table includes steps of selecting one of the entries, computing a pre-switching output value of the selected entry, which is determined by the predetermined function and one of the input signal values corresponding to the selected entry, switching the one of the input signal values in accordance with one of the switching values corresponding to the selected entry to produce a switched input signal value, computing a post-switch value of the selected entry which is determined by the predetermined function and the switched input signal value, comparing the pre-switch value with the post-switch value, and assigning a first predetermined value to the selected entry when the pre-switch value and the post-switch value are equal to each other, and a second predetermined value to the selected entry when the pre-switch value and the post-switch value are different from each other.
The switching of the input signal value preferably includes steps of representing the input signal value and the switching value with binary bits, and changing a binary bit of the input signal value to an inverse of the binary bit when a corresponding binary bit of the switch value indicates a switching.
The pre-switch value may be computed by providing the binary bits of the input signal value to the inputs of the circuit, wherein each of the binary bits of the input signal value is input to a corresponding one of the inputs, processing the binary bits received by the inputs in accordance with the predetermined function, and generating the pre-switch value as a result of the processing where the pre-switch value has binary bits. The post-switch value may be computed by providing binary bits of the switched input signal value to the inputs of the circuit, each of the binary bits of the switched input signal value being input to a corresponding one of the inputs, processing the binary bits of the switched input signal value received by the inputs in accordance with the predetermined function, and generating the post-switch value as a result of the processing, the post-switch value having binary bits.
The present invention also provides a method of computing a signal probability at the output of the circuit. The method includes steps of creating a truth table for the circuit in accordance with the predetermined function, the truth table having entries respectively corresponding to signals at the inputs, choosing in sequence one of entries each of which has a predetermined value representing that a signal at the output of the circuit switches, determining whether a signal at one of the inputs corresponding to the entry chosen is at logic high, assigning to the signal at the one of the inputs an event probability representing that the signal is at logic high, when the signal is determined to be at logic high, and accumulating event probabilities assigned to signals at inputs corresponding to entries chosen, respectively, whereby producing the signal probability at the output of the circuit. The above-described methods for computing switching probability and signal probability may be applied to a network having multiple logic circuits, wherein signal and switching probabilities at output of a logic circuit are provided to an input of another logic circuit connected to the logic circuit.
The present invention also provides a method for estimating power consumed in a network. The method preferably includes step of providing characteristics of each of the logic circuits, computing the signal and switching probabilities at output of each of the logic circuits, estimating a component power for each of the logic circuits with the characteristics provided and the signal and switching probabilities computed, and accumulating component powers estimated for the logic circuits, respectively, to produce the power consumed in the network. The method for estimating power may further include a step of estimating signal and switching probabilities at inputs of a logic circuit from signal and switching probabilities computed at a precedent stage, when the logic circuit receives no signal and switching probabilities from another logic circuit.
The present invention also provides a method for optimizing power consumed in the network. The method for optimizing power includes steps of estimating a pre-transform power for the network using the step of estimating power, performing synthesis transform with respect to each of the logic circuits in the network, estimating a post-transform power for the network using the step of estimating the power, upon the synthesis transform being performed, and accepting the synthesis transform based on values of the pre-transform power and the post-transform power estimated. The pre-transform power may be updated with the post-transform power until a stopping criterion is reached, whereby producing an optimized power for the network.
These and other objects, features and advantages of the present invention will become apparent from the following detailed description of the preferred embodiments thereof, which is to be read in conjunction with the accompanying drawings, wherein like elements are designated by identical reference numbers throughout the several views.